package org.example.dynamic_planning;

import java.util.Arrays;

public class Longest_callback_subroutine_sequence {
    public static void main(String[] args) {
        //最长回文子序列

        //给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
        //子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
        String s ="cbbd";
        int i = longestPalindromeSubseq(s);
        System.out.println(i);
    }
    public static int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j)){
                    if (i == j){
                        dp[i][j] = 1;
                    } else if (i - j == 1) {
                        dp[i][j] = 2;
                    }else {
                        dp[i][j] = dp[i-1][j+1] + 2;
                    }
                }else {
                    dp[i][j] = Math.max(Math.max(dp[i][j],dp[i-1][j]),dp[i][j+1]);
                }
            }
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[s.length()-1][0];
    }
}
